package tech.lixinlei.current.set;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class _187 {

    public static void main(String[] args) {
        String input = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        List<String> repeatedDnaSequences = new Solution().findRepeatedDnaSequences(input);
        repeatedDnaSequences.forEach(System.out::println);
    }

}

class Solution {

    public List<String> findRepeatedDnaSequences(String s) {
        int L = 10, n = s.length();
        HashSet<String> seen = new HashSet();
        HashSet<String> output = new HashSet();

        // iterate over all sequences of length L
        for (int start = 0; start < n - L + 1; ++start) {
            String tmp = s.substring(start, start + L);
            if (seen.contains(tmp)) {
                output.add(tmp);
            }
            seen.add(tmp);
        }
        return new ArrayList<>(output);
    }

}